package day19;

import java.util.HashMap;

/**
 * 给你一个整数数组nums，返回 nums中最长等差子序列的长度。
 *
 * 回想一下，nums 的子序列是一个列表nums[i1], nums[i2], ..., nums[ik] ，且0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果seq[i+1] - seq[i](0 <= i < seq.length - 1) 的值都相同，那么序列seq是等差的。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [3,6,9,12]
 * 输出：4
 * 解释：
 * 整个数组是公差为 3 的等差数列。
 * 示例 2：
 *
 * 输入：nums = [9,4,7,2,10]
 * 输出：3
 * 解释：
 * 最长的等差子序列是 [4,7,10]。
 * 示例 3：
 *
 * 输入：nums = [20,1,15,3,10,5,8]
 * 输出：4
 * 解释：
 * 最长的等差子序列是 [20,15,10,5]。
 *
 *
 */
public class Solution5 {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        HashMap<Integer,Integer> []maps=new HashMap[n];
        for (int i = 0; i < n; i++) {
            maps[i]=new HashMap<>();
        }
        int ans = 2;
        for (int i = 1; i < n; i++) {
            for(int j = i-1;j>=0;j--){
                int d = nums[i]-nums[j];
                int len = maps[j].getOrDefault(d,1);
                maps[i].put(d,Math.max(len+1,maps[i].getOrDefault(d,0)));
                ans = Math.max(ans,len+1);
            }
        }
        return ans;
    }
}
